
package com.huawei.common.okhttp;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * 功能描述
 *
 * @author cWX1142527
 * @since 2023年01月18日
 */
public class Java_239_滑动窗口最大值 {
    public static void main(String args[]) {
        Random random = new Random();
        int n = 20;
        for (int i = 0; i < n; i++) {
            // length = [1 - n]
            int length = random.nextInt(n) + 1;
            int[] nums = new int[length];
            for (int j = 0; j < length; j++) {
                nums[j] = random.nextInt(n);
            }
            System.out.print("原值：[");
            Arrays.stream(nums).forEach(a -> System.out.print(a + ","));
            System.out.println("]");
            // kVal = [1 - n]
            for (int k = 1; k < length + 1; k++) {
                int[] result = maxslidingWindowVals(nums, k);
                System.out.print("浮动窗口大小：" + k + "滑动窗口最大值：");
                Arrays.stream(result).forEach(x -> System.out.print(x + ","));
                System.out.println();
            }
        }
    }

    public static int[] maxslidingWindowVals(int[] nums, int kVal) {
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>((x, y) -> {
            return x[0] != y[0] ? y[0] - x[0] : y[1] - x[1];
        });
        for (int i = 0; i < kVal; i++) {
            priorityQueue.offer(new int[]{nums[i], i});
        }
        int n = nums.length;
        int[] result = new int[n - kVal + 1];
        result[0] = priorityQueue.peek()[0];
        for (int i = kVal; i < n; ++i) {
            priorityQueue.offer(new int[]{nums[i], i});
            while (priorityQueue.peek()[1] <= i - kVal) {
                priorityQueue.poll();
            }
            result[i - kVal + 1] = priorityQueue.peek()[0];
        }
        return result;
    }
}
